package algorithm.BinaryTree;

import java.util.Stack;

public class NonRecursiveOrder {
    public static class TreeNode{
        public int value;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val){
            this.value=val;
            left=right=null;
        }
    }
    public static void Do(TreeNode node){
        System.out.println(node.value);
    }

    /**
     * 非递归的前序遍历
     * @param node
     */
    public static void preOrder(TreeNode node){
        if(node!=null){
            Stack<TreeNode> stack=new Stack<>();
            stack.push(node);
            while(!stack.isEmpty()){
                node=stack.pop();
                Do(node);
                if(node.right!=null){
                    stack.push(node.right);
                }
                if(node.left!=null){
                    stack.push(node.left);
                }
            }
        }
    }

    /**
     * 非递归的中序遍历
     * @param node
     */
    public static void inOrder(TreeNode node){
        if(node!=null){
            Stack<TreeNode> stack=new Stack<>();
            while(node!=null||!stack.isEmpty()){
                if(node!=null){
                    //先把左孩子压到栈里
                    stack.push(node);
                    node=node.left;
                }else{
                    //没有左孩子了就执行自己，然后执行右子树
                    node=stack.pop();
                    Do(node);
                    node=node.right;
                }
            }
        }
    }

    /**
     * 使用两个栈实现后序遍历
     * 变体前序遍历：中右左
     * 倒置之后即后序遍历：左右中
     * @param node
     */
    public static void posOrderWithTwoStacks(TreeNode node){
        if(node!=null){
            Stack<TreeNode> stack=new Stack<>();
            Stack<TreeNode> collect=new Stack<>();
            stack.push(node);
            while(!stack.isEmpty()){
                node=stack.pop();
                //这里用从stack倒出元素压入collect代替了do，实现了stack栈的倒置
                collect.push(node);
                if(node.left!=null){
                    stack.push(node.left);
                }
                if(node.right!=null){
                    stack.push(node.right);
                }
            }
            while(!collect.isEmpty()){
                Do(collect.pop());
            }
        }
    }

    /**
     * 用一个栈实现后序遍历
     * 增加一个哨兵节点，用来指示上一个被打印的节点。
     * @param node
     */
    public static void posOrderWithOneStack(TreeNode node){
        if(node!=null){
            Stack<TreeNode> stack=new Stack<>();
            stack.push(node);
            while(!stack.isEmpty()){
                TreeNode cur=stack.peek();
                if(cur.left!=null&&node!=cur.left&&node!=cur.right){
                    stack.push(cur.left);
                }else if(cur.right!=null&&node!=cur.right){
                    stack.push(cur.right);
                }else{
                    node=stack.pop();
                    Do(cur);
                }
            }
        }
    }
}
